package main

func longestPalindrome(s string) string {
	n := len(s)
	if n == 0 || n == 1 {
		return s
	}
	dp := make([][]bool, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]bool, n)
	}
	ans := ""
	for l := 0; l < n; l++ {
		for i := 0; i < n; i++ {
			j := i + l // sub string: s[i:j+1]
			if j >= n {
				continue
			}
			if l == 0 {
				dp[i][j] = true
			} else if l == 1 {
				if s[i] == s[j] {
					dp[i][j] = true
				}
			} else {
				if s[i] == s[j] && dp[i+1][j-1] {
					dp[i][j] = true
				}
			}
			if dp[i][j] && j-i+1 > len(ans) {
				ans = s[i : j+1]
			}
		}
	}
	return ans
}

func longestPalindrome2(s string) string {
	if len(s) == 0 || len(s) == 1 {
		return s
	}
	ans := ""
	for i := 0; i < len(s); i++ {
		ans1 := expand(s, i, i)
		if len(ans1) > len(ans) {
			ans = ans1
		}
		ans2 := expand(s, i, i+1)
		if len(ans2) > len(ans) {
			ans = ans2
		}
	}
	return ans
}

func expand(s string, i, j int) string {
	ans := ""
	for i >= 0 && j < len(s) {
		if s[i] == s[j] {
			ans = s[i : j+1]
		} else {
			break
		}
		i--
		j++
	}
	return ans
}

func main() {
	println(longestPalindrome("babad"))
	println(longestPalindrome("aa"))
	println(longestPalindrome2("babad"))
	println(longestPalindrome2("aa"))
}
